/**
 * @file doublelinkedlist.h
 * @author 冯皓
 * @brief 
 * @version 0.1
 * @date 2022-10-07
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <iostream> 
#include <algorithm> 
#include <limits>
using namespace std;
template <typename Object>
class List{
    private:
	/**
	 * @brief 定义拥有一个数字和两个指针的结构从而建立链表
	 * 
	 */
		struct Node{
			Object data;
			Node *prev;
			Node *next;
			Node( const Object & d = Object{ }, Node * p = nullptr,
			Node * n = nullptr )
			: data{ d }, prev{ p }, next{ n}{}
			Node( Object && d, Node * p = nullptr, Node * n = nullptr )
			: data{ std::move( d ) }, prev{ p }, next{ n}{} 
		};
	public:
		class const_iterator{
			public:
            	/**
             	* @brief 构造函数
             	* 
             	*/
				const_iterator( ) : current{ nullptr }
					{ }
				/**
			 	* @brief *的运算符重载
			 	* 
			 	* @return const Object& 
			 	*/
				const Object & operator* ( ) const
					{ return retrieve( ); }
				/**
			 	* @brief ++的运算符重载
			 	* 
			 	* @return const_iterator& 
			 	*/
				const_iterator & operator++ ( )
				{
					current = current->next;
					return *this;
				}
			
				const_iterator operator++ ( int )
				{
					const_iterator old = *this;
					++( *this );
					return old;
				}
				bool operator== ( const const_iterator & rhs ) const
					{ return current == rhs.current; }
				bool operator!= ( const const_iterator & rhs ) const
					{ return !( *this == rhs ); }
			protected:
				Node *current;
				Object & retrieve( ) const
				{ return current->data; }
				const_iterator( Node *p ) : current{ p }
				{ }
				friend class List<Object>;
		};
		class iterator : public const_iterator
		{
			public:
				iterator( )
					{ }
				Object & operator* ( )
					{ return const_iterator::retrieve( ); }
				const Object & operator* ( ) const
					{ return const_iterator::operator*( ); }
				iterator & operator++ ( )
				{
					this->current = this->current->next;
					return *this;
				}
				iterator operator++ ( int )
				{
					iterator old = *this;
					++( *this );
					return old;
				}
			protected:
				iterator( Node *p ) : const_iterator{ p }
					{ }
				friend class List<Object>;
		};
	public:
		/**
		 * @brief 普通构造函数
		 * 
		 */
		List(){
			init( );
		}
		/**
		 * @brief 拷贝构造函数
		 * 
		 * @param rhs 
		 */
		List(const List &rhs){
			init( );
			for( auto & x : rhs )
			push_back( x );
		}
		/**
		 * @brief 析构函数
		 * 
		 */
		~List(){
			clear( );
			delete head;
			delete tail;
		}
		List & operator=(const List & rhs){
			List copy = rhs;
			std::swap( *this, copy );
			return *this;
		}
		List (List && rhs)
			: theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
		{
			rhs.theSize = 0;
			rhs.head = nullptr;
			rhs.tail = nullptr;
		}
		List & operator= (List && rhs) {
			std::swap( theSize, rhs.theSize );
			std::swap( head, rhs.head );
			std::swap( tail, rhs.tail );
			return *this;
		}
		/**
		 * @brief 链表的头
		 * 
		 * @return iterator 
		 */
		iterator begin( )
		{ return { head->next }; }
		const_iterator begin( ) const
		{ return { head->next }; }
		/**
		 * @brief 链表的尾
		 * 
		 * @return iterator 
		 */
		iterator end( )
		{ return { tail }; }
		const_iterator end( ) const
		{ return { tail }; }
		
		int size( ) const
		{ return theSize; }
		/**
		 * @brief 判断是否为空
		 * 
		 * @return true 
		 * @return false 
		 */
		bool empty( ) const
		{ return size( ) == 0; }
		/**
		 * @brief 清空链表
		 * 
		 */
		void clear( )
		{
		while( !empty( ) )
		pop_front( );
		}
		Object & front( )
		{ return *begin( ); }
		const Object & front( ) const
		{ return *begin( ); }
		Object & back( )
		{ return *--end( ); }
		const Object & back( ) const
		{ return *--end( ); }
		/**
		 * @brief 在链表前插入
		 * 
		 * @param x 
		 */
		void push_front( const Object & x )
		{ insert( begin( ), x ); }
		void push_front( Object && x )
		{ insert( begin( ), std::move( x ) ); }
		/**
		 * @brief 在链表后插入
		 * 
		 * @param x 
		 */
		void push_back( const Object & x )
		{ insert( end( ), x ); }
		void push_back( Object && x )
		{ insert( end( ), std::move( x ) ); }
		/**
		 * @brief 在链表头删除
		 * 
		 */
		void pop_front( )
		{ erase( begin( ) ); }
		/**
		 * @brief 在链表尾部删除
		 * 
		 */
		void pop_back( )
		{ erase( --end( ) ); }
		/**
		 * @brief 从链表中间插入
		 * 
		 * @param itr 
		 * @param x 
		 * @return iterator 
		 */
		iterator insert( iterator itr, const Object & x )
		{ 
			Node *p = itr.current;
			theSize++;
			return { p->prev = p->prev->next = new Node{ x, p->prev, p } };
		} 
		iterator insert( iterator itr, Object && x )
		{
			Node *p = itr.current;
			theSize++;
			return { p->prev = p->prev->next
			= new Node{ std::move( x ), p->prev, p } };
		}
		/**
		 * @brief 从链表中间删除
		 * 
		 * @param itr 
		 * @return iterator 
		 */
		iterator erase( iterator itr )
		{ 
			Node *p = itr.current;
			iterator retVal{ p->next };
			p->prev->next = p->next;
			p->next->prev = p->prev;
			delete p;
			theSize--;
			return retVal;
		}
		iterator erase( iterator from, iterator to )
		{
			for( iterator itr = from; itr != to; )
				itr = erase( itr );
			return to;
		}

		void print()
		{
			iterator flag=this->begin();
			while(flag!=this->end())
			{
				cout<<*flag ;
				flag++;
			}
    	}

	private:
		int theSize;
		Node *head;
		Node *tail;
		void init( )
		{
		theSize = 0;
		head = new Node;
		tail = new Node;
		head->next = tail;
		tail->prev = head;
		}
};